package src;

/**
 * 大根堆
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    public MaxHeap(){
        this(10);
    }
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for (int i = parent(data.getSize() - 1); i >= 0 ; i--) {
            shifDown(i);
        }
    }

    public int getSize(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    private int parent(int index){
        if (index == 0) {
            throw new IllegalArgumentException("index:0 not exist parent");
        }
        return (index - 1) / 2;
    }
    private int leftChild(int index){
        return index * 2 + 1;
    }
    private int rightChild(int index){
        return index * 2 + 2;
    }

    public void add(E e){
        data.addLast(e); // 添加元素到末尾
        // 调整数组，以符合大根堆的性质
        siftUp(data.getSize() - 1);
    }

    private void siftUp(int k){
        while (k > 0){
            // 当前节点的值大于父节点的值，则交换
            if (data.get(k).compareTo(data.get(parent(k))) > 0) {
                data.swap(k, parent(k));
                k = parent(k);
            }else{
                break;
            }
        }
    }

    private void shifDown(int k){
        // 极端的结束条件，当前节点无左右孩子节点
        while(leftChild(k) < data.getSize()){
            // 先找出左右孩子中最大的，再与根节点比较并交换
            int maxChildIndex = leftChild(k);
            if (rightChild(k) < data.getSize()
                // 右孩子存在，并且比左孩子的值大
                && data.get(rightChild(k)).compareTo(data.get(maxChildIndex)) > 0){
                maxChildIndex = rightChild(k);
            }
            if (data.get(k).compareTo(data.get(maxChildIndex)) < 0) {
                data.swap(k, maxChildIndex);
                k = maxChildIndex;
            }else{
                break;
            }
        }
    }

    public E popMax(){
        E ret = getMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        shifDown(0);
        return ret;
    }

    public E getMax(){
        if (data.getSize() == 0) {
            throw new IllegalArgumentException("can't findMax when is empty");
        }
        return data.get(0);
    }

    public E replace(E e){
        E ret = getMax();
        data.set(0, e);
        shifDown(0);
        return ret;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("MaxHeap: ");
        res.append(data.toString());
        return res.toString();
    }
}